package 数学作业.homework3.test1;

import java.util.Random;

public class 堆排序 {
    public static void swap(int[] arr,int left,int right){
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
    public static void shiftDown(int[] arr,int size,int parent){//size是边界，就是向下调整的最后一个可调整的节点的位置
        int child = parent * 2 + 1;
        //确保如果要交换的话，那个孩子节点是两个当中较大的那个。
        while(child < size){
            if(child + 1 < size && arr[child + 1] > arr[child]){
                child += 1;
            }
            //接下来进行交换，并且
            if(arr[parent] < arr[child]){
                swap(arr,parent,child);
                parent = child;
                child = parent * 2 + 1;
            }else{
                return;
            }
        }
    }
    public static void heapSort(int[] arr){
        int size = arr.length;
        for(int root = (arr.length-2)/2; root >= 0; root--){
            shiftDown(arr, arr.length, root);
        }
        int end = size - 1;
        while(end != 0){
            swap(arr,0,end);
            shiftDown(arr,end,0);
            end--;
        }
    }

    public static void main(String[] args) {
        Random ran = new Random();
        int[] arr = new int[100];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = ran.nextInt(101);
        }
        heapSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
